#include <stdio.h>
#include <stdlib.h>
#include <time.h>

typedef int ElemType;
typedef struct {
    ElemType lenth;
    ElemType *str;
} SSTable;

void SST_Init(SSTable &T, int len) {
    T.lenth = len;
    T.str = (ElemType *) malloc(sizeof(ElemType) * T.lenth);
    srand(time(NULL));
    for (int i = 0; i < T.lenth; i++) {
        T.str[i] = rand() % 100;
    }
}

void array_print(SSTable T) {
    for (int i = 0; i < T.lenth; i++) {
        printf("%3d", T.str[i]);
    }
    printf("\n");
}

void swap(int &a, int &b) {
    a ^= b;
    b ^= a;
    a ^= b;
}
//插入排序
void InsertSort(ElemType *str, int n) {
    int insertVal, i, j;
    for (i = 1; i < n; i++) {//外层循环控制插入的数
        insertVal = str[i];//保存我们要插入的数
        //内层循环控制比较，j要大于等于0，同时str[j]大于insertval时，str[j]位置元素往后覆盖
        for (j = i - 1; j >= 0 && str[j] > insertVal; j--) {
            str[j + 1] = str[j];
        }
        str[j + 1] = insertVal;//把要插入的元素放对应的位置
    }
}

int main() {
    SSTable T;
    //初始化顺序表
    SST_Init(T, 10);
    array_print(T);
    //插入排序
    InsertSort(T.str, T.lenth);
    array_print(T);
    return 0;
}
